package greedy;

/**
 * 跳跃游戏
 */
public class JumpGame {

    public static void main(String[] args) {
        int[] paces = new int[] {3,2,1,0,4};
        int maxIndex = 0;
        for (int i = 0; i < paces.length; i++) {
            // 每次都更新当前范围内最大步长能到达的索引
            maxIndex = getMaxPaceIndexInCurrPace(i, paces);
        }
        System.out.println(maxIndex >= paces.length - 1);
    }

    /**
     *  获取当前步长范围内 最大值的索引
     * @param index
     * @param paces
     * @return
     */
    private static int getMaxPaceIndexInCurrPace(int index,int[] paces) {
        int maxValIndex = index;
        int endIndex = Math.min(index+paces[index], paces.length);
        for (int i = index; i < endIndex; i++) {
            if (paces[i] > paces[maxValIndex]) {
                maxValIndex = i;
            }
        }
        return maxValIndex;
    }
}
